'''
Problem 1
假设存在一个正整数 n，它加上 100 是一个完全平方数，加上 168 也是一个完全平方数，求 n。
'''

# (n + 100) ** 0.5 必然是一个整数
# (n + 168) ** 0.5 必然是一个整数
# (n + 100) ** 0.5 == int((n + 100) ** 0.5) -> n + 100 是一个完全平方数


n = 1

while True:
    if (n + 100) ** 0.5 == int((n + 100) ** 0.5) and (n + 168) ** 0.5 == int((n + 168) ** 0.5):
        print(n)
        break
    else:
        n += 1

'''
Problem 2
按照顺序输入 年 月 日（假定输入的年月日都是合法的），判断输入的这一天是这一年的第几天。
2021
1
31
'''
# year = int(input("Year:"))
# month = int(input("Month:"))
# day = int(input("Day:"))

# day_of_month = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31]

# def is_leap_year(y):
#     # 能被 400 整除的一定是闰年
#     # or
#     # 能被 4 整除但是不能被 100 整除的是闰年
#     return y % 400 == 0 or (y % 4 == 0 and y % 100 != 0)

# if is_leap_year(year):
#     day_of_month[2] += 1

# ans = 0

# for m in range(0, month):
#     ans += day_of_month[m]

# ans += day

# print(ans)

'''
Problem 3
输入三个正整数，列出这三个数字的所有组合。
'''
import itertools

# x = int(input("x:"))
# y = int(input("y:"))
# z = int(input("z:"))

# arr = [x, y, z]

# for v in itertools.permutations(arr, 3):
#     print(v)

# # 把输入的数字从大到小排序
# arr.sort(reverse = True)

'''
Problem 4
Fibonacci

递归：
1. 终结条件：递归停止的条件是什么
2. 递归公式：递归调用的过程
'''

def fibonacci(n):
    if n == 0 or n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2);

import itertools

'''
Problem 5
题目: 有四个数字: 1、2、3、4

1. 这四个数字能组成多少个互不相同且无重复数字的三位数？

2. 这些数字各是多少？

for 百位数字 in 1...4:
    for 十位数字 in 1...4:
        for 各位数字 in 1...4:
            if 百位数字 != 十位数字 != 各位数字:
                计数+1

print(计数)

123
234
432

n 个里面取 k 个的排列
'''
numbers = [1, 2, 3, 4]
numbers.sort() # 从小到大排序
numbers.sort(reverse=True)



count = 0
for number in itertools.permutations(numbers, 3):
    count += 1
    
    n = number[0]*100 + number[1]*10 + number[0]
    print(n)
    

'''
Problem 6
某个公司采用公用电话传递数据, 数据是四位的整数，在传递过程中是加密的, 加密规则如下:

每位数字都加上5, 然后用和除以10的余数代替该数字, 再将第一位和第四位交换, 第二位和第三位交换。

输入一个四位数字，返回加密后的结果

1234 % 10
1234 // 100
1234 % 100 // 10
1234 % 1000 // 100


1
2
3
4

16789
'''
def encode(number):
    digits = []

    t = number // 1000
    h = number % 1000 // 100
    n = number % 100 // 10
    d = number % 10

    t = (t + 5) % 10
    h = (h + 5) % 10
    n = (n + 5) % 10
    d = (d + 5) % 10

    result = d * 1000 + t + n * 100 + h * 10
    return result

print(encode(1234))

'''
Problem 7

[2, 1, 2, 2, 2, 3, 4, 2]

编写一个函数
把数组中，值为 k 的元素，都移动到数组的末尾
moving_elements_to_end([2, 1, 2, 2, 2, 3, 4, 2], 2)
       vJ
[4, 1, 3, 2, 2, 2, 2, 2]
    ^I

只要 I != J

如果 arr[J] == k -> J -= 1
如果 arr[I] == k -> 交换 I J 位置上的元素
'''

def moving_elements_to_end(arr, k):
    i = 0
    j = len(arr) - 1

    while i < j:
        # 如果 arr[j] == k，不停的把 k 向前移动
        while i < j and arr[j] == k:
            k -= 1
        
        if arr[i] == k:
            arr[i], arr[j] = arr[j], arr[i]
        
        i += 1
    
    return arr